/*
 * Author: Wang Hsutung
 * Date: 2015/12/04
 * Locale: Wuhan, Hubei
 * Email: hsu[AT]whu.edu.cn
 */
#include <iostream>
#include <string>
#include <stack>

template <class Type> struct TreeNode {
    Type val;
    TreeNode <Type> *left;
    TreeNode <Type> *right;

    TreeNode <Type> (Type c, TreeNode <Type> *l = NULL, TreeNode <Type> *r = NULL) :
        val (c), left (l), right (r) {}

    static void printFrom (TreeNode <Type> *p, std::string prefix = "")
    {
        if (p == NULL) {
            std::cout << "(null)\n";
            return;
        }
        std::cout << p->val << "\n";

        if (p->left || p->right) {
            std::cout << prefix << "├── ";
            printFrom (p->left, prefix + "│   ");
            std::cout << prefix << "└── ";
            printFrom (p->right, prefix + "    ");
        }
    }
};

template <class Type> struct BinTree {
    TreeNode <Type> *root;

    void print (void)
    {
        TreeNode <Type>::printFrom (root);
    } bool isBinarySearchTree (void)
    {
        if (root == NULL)
            return false;

        std::stack <TreeNode <Type> *> nodeStk;
        std::stack <bool> isVisitedStk;
        TreeNode <Type> *prev = NULL, *p = NULL;
        nodeStk.push (root);
        isVisitedStk.push (false);

        while (!nodeStk.empty() ) {
            p = nodeStk.top();
            nodeStk.pop();
            bool isVisited = isVisitedStk.top();
            isVisitedStk.pop();


            if (isVisited) {
                if (prev != NULL && prev->val >= p->val)
                    return false;
                prev = p;
            } else {
                if (p->right != NULL) {
                    nodeStk.push (p->right);
                    isVisitedStk.push (false);
                }
                nodeStk.push (p);
                isVisitedStk.push (true);
                if (p->left != NULL) {
                    nodeStk.push (p->left);
                    isVisitedStk.push (false);
                }
            }
        }
        return true;
    }
};

int main (void)
{
    const char *str[] = { "No", "Yes" };
    typedef TreeNode <int>TNode;

    BinTree <int>tree_a;
    tree_a.root = new TNode (4);
    tree_a.root->left = new TNode (2);
    tree_a.root->right = new TNode (7);
    tree_a.root->right->left = new TNode (6);
    tree_a.root->right->right = new TNode (8);
    tree_a.root->left->left = new TNode (1);
    tree_a.root->left->right = new TNode (3);
    tree_a.root->right->left->left = new TNode (5);

    std::cout << "Is TREE_A (structed as follows) a BST? "
              << str[tree_a.  isBinarySearchTree ()] << std::endl;
    tree_a.print();


    BinTree <int>tree_b;
    tree_b.root = new TNode (1);
    tree_b.root->left = new TNode (2);
    tree_b.root->right = new TNode (3);
    tree_b.root->right->left = new TNode (4);
    tree_b.root->right->right = new TNode (5);
    tree_b.root->right->right->right = new TNode (9);
    tree_b.root->left->left = new TNode (6);
    tree_b.root->left->left->right = new TNode (8);
    tree_b.root->left->right = new TNode (7);

    std:: cout << "\nIs TREE_B (structed as follows) a BST ? "
               << str[tree_b.  isBinarySearchTree ()] << std::endl;
    tree_b.print();

    return 0;
}
